package com.wzl.algorithm;

/**插入排序
 * 插入排序思路：
 * 1. 从第一个元素开始，该元素可以认为已经被排序
 * 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
 * 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
 * 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 * 5. 将新元素插入到该位置后
 * 6. 重复步骤2~5
 * 参考动画 https://www.bilibili.com/video/av18980488?from=search&seid=6655316340843212728
 * @author weiZhiLin
 * @version 1.0
 * @date 2020/1/9 13:58
 */
public class InsertSort {
    public static int[] sort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int i1 = a[i];
            // 注意是从 0 到 i ，在已经排序好的队列中插入
            for (int j = 0; j < i; j++) {
                int i2 = a[j];
                if (i1 > i2) {
                    a = SortUtils.arraySwap(a, i, j);
                }
            }
        }
        SortUtils.printArr(a);
        return a;
    }
}
